// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
public class LinkedListCycleII {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode detectCycle(ListNode head) {
        if(head == null || head.next ==null) {
            return head;
        }

        ListNode fast = head, slow = head;

        boolean flg = false;
        //找到相遇点
        while (fast.next != null && fast.next.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) { //证明有环
                flg = true;
                break;
            }
        }
        if(!flg) {
            return null;
        }

        fast = head;  //让fast回到起点位置
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}
